Выпуклая оптимизация: Геометрические основы выпуклой оптимизации

Представьте, что вы перемещаетесь по сложной местности, где ваша цель — найти ближайшую точку к безопасности. На языке оптимизации эта «безопасность» — это множество $C$, а действие нахождения ближайшей точки называется проекцией. Хотя интуиция подсказывает, что всегда существует одна-единственная «ближайшая» точка, математическая реальность оказывается более тонкой. Геометрическая основа выпуклой оптимизации заключается в формализации понятия «близости», выходящем за рамки евклидовой интуиции, и переходящем к строгим функциональным представлениям, таким как индикаторные и функции поддержки.

1. Проекции и расстояния

Расстояние от точки $x_0$ до множества $C$ определяется как нижняя грань всех возможных расстояний до точек внутри множества:

$\text{dist}(x_0, C) = \inf\{\|x_0 - x\| \mid x \in C\}$

Конкретный оптимизатор, достигающий этого расстояния, называется оператором проекции:

$P_C(x_0) = \text{argmin}\{\|x - x_0\| \mid x \in C\}$

Для простого гиперплоскости, определённой уравнением $a^T x = b$, проекция имеет красивое аналитическое решение: $P_C(x_0) = x_0 + (b - a^T x_0)a/\|a\|_2^2$. Однако для общих множеств это остаётся задачей с ограничениями: минимизировать $\|x - x_0\|$ при условии $f_i(x) \leq 0$ и $Ax = b$.

2. Функциональная геометрия

Чтобы рассматривать геометрические ограничения как компоненты целевой функции, мы используем два мощных функциональных «зеркала»:

Функция индикатора $I_C(x)$: $I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}$. Это превращает геометрию в численную штрафную функцию.
Функция поддержки $S_C(x)$: $S_C(x) = \sup_{y \in C} x^T y$. Это характеризует множество через его границы-гиперплоскости во всех направлениях.

Теорема: Теорема Мотзкина

Непустое, замкнутое множество $C \in \mathbf{R}^n$ является множеством Чебышёва (обладающим уникальной проекцией для каждого $x_0$), если и только если оно выпукло.

Эскиз доказательства (единственность)

Предположим, что $C$ выпукло, а норма строго выпукла. Если бы существовало две различные ближайшие точки $u, v \in C$, такие что $\|u - x_0\| = \|v - x_0\| = d$, то их середина $w = (u+v)/2$ принадлежала бы $C$ (по выпуклости).

По строгой выпуклости нормы: $\|w - x_0\| = \|\frac{1}{2}(u - x_0) + \frac{1}{2}(v - x_0)\| < \frac{1}{2}\|u - x_0\| + \frac{1}{2}\|v - x_0\| = d$.

Это противоречит предположению, что $d$ — минимальное расстояние. Следовательно, проекция должна быть единственной.

Оговорка 8.4: Зависимость от нормы

Мы часто строим разделяющую гиперплоскость по формуле: $(P_C(x_0) - x_0)^T (x - (1/2)(x_0 + P_C(x_0))) = 0$. Осторожно! Такая конструкция верна только для только для евклидовой нормы. Для обобщённых норм требуется более тонкое рассмотрение ортогональности.

🎯 Ключевая идея

Выпуклость — это «клей», обеспечивающий устойчивость в геометрической оптимизации. Без неё даже простая задача «нахождения ближайшей точки» может привести к нескольким конфликтующим решениям, что вызывает алгоритмическую нестабильность.

ВОПРОС 1

Согласно теореме Мотзкина, какие необходимые и достаточные условия должны выполняться для непустого, замкнутого множества в $\mathbf{R}^n$, чтобы оно было множеством Чебышёва?

Оно должно быть ограниченным и открытым.

Оно должно быть выпуклым.

Оно должно содержать начало координат.

Оно должно быть подпространством.

ВОПРОС 2

Каково аналитическое решение для проекции точки $x_0$ на гиперплоскость $a^T x = b$ в евклидовом пространстве?

P_C(x₀) = x₀ + (b - aᵀx₀)a / ||a||₂²

P_C(x₀) = x₀ - (b + aᵀx₀)a / ||a||₂

P_C(x₀) = (b / aᵀx₀)a

P_C(x₀) = x₀ + aᵀx₀ / b

ВОПРОС 3

Почему проекция на множество матриц ранга $k$ (Пример 8.2) может не быть уникальной?

Множество не выпукло.

Множество не замкнуто.

Ранг всегда линейное свойство.

У матриц нет норм.

ВОПРОС 4

Какая функция позволяет представить множество $C$ как штраф в целевой функции, возвращая 0, если точка принадлежит множеству, и ∞ в противном случае?

Функция поддержки $S_C(x)$

Функция индикатора $I_C(x)$

Функция расстояния $\text{dist}(x, C)$

Матрица Грама

ВОПРОС 5

Верно или неверно: построение разделяющей гиперплоскости с использованием середины между $x_0$ и её проекцией работает для любой нормы.

Верно

Неверно

Кейс: Планирование траектории робота

Геометрические ограничения в системах реального времени

Роботизированный манипулятор отслеживает цель в точке $x_0 = [0, 0]^T$, но должен избегать «запрещённой зоны», определяемой не выпуклой границей единичного квадрата: $C = \{x \in \mathbf{R}^2 \mid \|x\|_\infty = 1\}$. Алгоритм управления пытается найти наиболее безопасную конфигурацию, решая задачу $\text{minimize } \|x - x_0\|$ при условии $x \in C$.

Вопрос 1

Определите проекцию $P_C(x_0)$ и обсудите последствия для стабильности управления роботом.

Решение:
Для $x_0 = 0$ и $C$, являющегося границей единичного квадрата, имеется четыре равноудалённые точки: $[1, 0], [-1, 0], [0, 1], [0, -1]$, все на расстоянии $d=1$.

Последствие: Поскольку множество не выпукло, проекция не является уникальной. Это может вызвать «дребезг» или алгоритмическую нестабильность, при которой контроллер робота быстро переключается между четырьмя оптимальными целями, потенциально повреждая аппаратное обеспечение.

Вопрос 2

Как можно сформулировать минимизацию расстояния в форме «Y» для робота, избегающего полиэдральной запрещённой зоны $Ax \le b$?

Решение:
Задача моделируется как:
$$\text{minimize } \|y\|$$
$$\text{subject to } Ax \le b, \quad x_0 - x = y$$
Где $y$ представляет собой свободный член или «вектор расстояния» между текущей целью $x_0$ и допустимой точкой $x$. Если зона является полиэдром, задача сводится к стандартной квадратичной программе (QP) для евклидовой нормы.